package SortAlgorithm;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] a=new int[]{67, 10, 29 ,90 ,32 ,100 ,96 ,24 ,55 ,27};
        System.out.println(Arrays.toString(a));
        mergeSort(a,0,a.length-1);
        System.out.println(Arrays.toString(a));
    }
    //递归实现
    public static void mergeSort(int[] arr,int L,int R){
        if(L<R){
            int mid=L+((R-L)>>1);
            mergeSort(arr,L,mid);
            mergeSort(arr,mid+1,R);
            merge(arr,L,mid,R);
        }
    }
    public static void merge(int[] arr,int L,int mid, int R){
        int[] help=new int[arr.length];
        help= Arrays.copyOf(arr,arr.length);
        int cur=L;
        int left=L;
        int right=mid+1;
        while(left<=mid&&right<=R){
            if(help[left]<=help[right]){
                arr[cur++]=help[left++];
            }else{
                arr[cur++]=help[right]++;
            }
        }
        while(left<=mid){
            arr[cur++]=help[left++];
        }
    }
}
